Program debugging is the process of identifying and fixing software bugs. Debugging is a difficult and time-consuming task. Various software methodologies have been presented to simplify this sometimes arduous task. At a high level, debugging is composed of three steps: observing symptoms, identifying root cause(s), and then fixing and testing. Among these steps, identifying the root causes is the most difficult, thus the most expensive, step of all. The space of potential root causes for failures is often proportional to the size and complexity of programs and almost always too large to be explored exhaustively. Developers often take a slice of the statements involved in a failure, hypothesize a set of potential causes in an ad hoc manner, and iteratively verify and refine their hypotheses until root causes are located. Obviously, this process can be quite tedious and time-consuming. Furthermore, the lack of access and/or familiarity to the source code can severely hinder the developers' ability to anticipate a “good” set of hypotheses and verify them.
Debugging tools all have the same ultimate goal—to narrow down the potential root causes for developers; but they have different ways to achieve that goal. These different approaches often leverage static and dynamic program analysis to detect anomalies or dependencies in the code, with one notable exception, namely Delta Debugging. [See Andreas Zeller, “Isolating Cause-Effect Chains from Computer Programs,” Proc. ACM SIGSSOFT, 10th International Symposium on the Foundations of Software Engineering (FSE-10), Charleston, S.C., November 2002]. Delta debugging is different in the sense that it is empirical. The fault localization information provided by current state-of-the-art techniques is often in the form of slices of program states that may lead to failures or slices of automatically identified likely program invariants that are violated or slices of the code that look suspicious.
Although these approaches can be quite effective, they suffer from three major limitations: 1) an inability to deal with conceptual errors; 2) requirement for both one passing and one failing run of a test case to perform debugging; and 3) a dependence on access to source code or binaries. Current approaches mainly target coding errors. They may not track down missing and/or misinterpreted program requirements. Note that we define a failure as the inability of a system or component to perform its required function. For example, consider the functional requirements of the deposit function for an automated teller machine (ATM). In its simplest form it can be expressed as balance=balance+amt, where balance is the balance of the account and amt is the amount to be deposited. Now assume that the implementation fails to update the balance or fails to commit the updated balance to a database. Tools that rely on static and dynamic analysis may not be able to find it; in general, what is not in the code/execution cannot be analyzed. Empirical tools may not find it either; they often require at least one passing and one failing run in order to perform their functions and in this case there may not be a passing run.
In one form or another, current approaches rely on accessing source code or binaries. However, this is not always possible for programs composed of remote third-party components such as Web Services. In such cases, the quality of results obtained from these tools could be severely degraded. As more and more systems built with commercial off-the-shelf (COTS) components and service-oriented architectures (SOA) are gaining momentum, the importance of being able to debug systems composed of many black-boxes is increasing.
Model-based testing (MBT) is one of the fields that has been extensively leveraging finite state models. In MBT, test cases are automatically derived from a given model and are in the form of an input and output sequence. The program is fed with the input sequence and its output is compared to the expected output. Although matching program and model outputs increases our confidence in the correctness of the program, it is barely adequate. For example, consider the finite state machine (FSM) model (M) given in FIG. 2 and a program (P) attempting to implement this model. P is a black box; its inputs and outputs can be observed, but no other information regarding its condition is known. Now, assume that P incorrectly implements the transition A−a/x→B as A−a/x→C. A legitimate test case (derived from M) to test the original transition is composed of the single input a, assuming that we are already in A. Although P gives the expected output when fed with a, a leaves P in a wrong state, which can manifest itself later as a failure. Therefore, the state of P after executing a should also be verified.
There is a need for a method of program debugging to overcome the shortcomings of the prior art.